/**
 * 72. 编辑距离
 * https://leetcode-cn.com/problems/edit-distance/
 */

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function minDistance(word1, word2) {
  const { length: length1 } = word1;
  const { length: length2 } = word2;
  const dp = new Array(length1 + 1);
  for (let i = 0; i <= length1; i += 1) {
    dp[i] = new Array(length2 + 1).fill(0);
  }
  for (let i = 1; i <= length1; i += 1) {
    dp[i][0] = i;
  }
  for (let j = 1; j <= length2; j += 1) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= length1; i += 1) {
    const preI = i - 1;
    for (let j = 1; j <= length2; j += 1) {
      const preJ = j - 1;
      const char1 = word1.charCodeAt(preI);
      const char2 = word2.charCodeAt(preJ);
      if (char1 === char2) {
        dp[i][j] = Math.min(dp[preI][j] + 1, dp[i][preJ] + 1, dp[preI][preJ]);
      } else {
        dp[i][j] = Math.min(dp[preI][j] + 1, dp[i][preJ] + 1, dp[preI][preJ] + 1);
      }
    }
  }
  return dp[length1][length2];
}

console.log(minDistance('horse', 'ros') === 3);
console.log(minDistance('intention', 'execution') === 5);
console.log(minDistance('intention', '') === 9);
console.log(minDistance('', 'execution') === 9);
console.log(minDistance('', '') === 0);
